import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-07-21
 * Time: 0:21
 */
public class PriorityQueues {
    public int[] arr;
    public int size;
    public int sizemax;

    public PriorityQueues() {
        arr=new int[10];
        size=0;
        sizemax=10;
    }

    //创建堆
    public void createHeap(int[] array) {
        size=array.length;
        for (int i = 0; i < size; i++) {
            arr[i]=array[i];
        }
        int n=(size-1)/2;
        while(n>=0){
            shiftDown(n);
            n--;
        }
    }

    /**大根堆
     * @param root 是每棵子树的根节点的下标
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root) {
        int c=root*2+1;
        if(c>=size){
            return;
        }
        while(c<size){
            if(c+1<size&&arr[c]<arr[c+1]){
                c++;
            }
            if(arr[root]>=arr[c]){
                break;
            }
            else{
                fun(root,c);
            }
            root=c;
            c=root*2+1;
        }
    }


    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()){
            arr= Arrays.copyOf(arr,size*2);
        }
        arr[size]=val;
        shiftUp(size);
        size++;
    }

    private void shiftUp(int child) {
        if (child == 0) {
            return;
        }
        int root=child;
        int c=child;
        while (root!=0) {
            c=root;
            root=(c-1)/2;
            if (arr[c] > arr[root]) {
                fun(c, root);
            }
        }
    }

    //判断是否为满
    public boolean isFull() {
        if(size==sizemax){
            return true;
        }
        return false;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() {
        if(size==0||size==1){
            return;
        }
        fun(0,size-1);
        size--;
        shiftDown(0);
    }

    //判断是否为空
    public boolean isEmpty() {
        if(size==0){
            return true;
        }
        return false;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        if(size==0){
            return -1;
        }
        return arr[size-1];
    }

    public void fun(int i,int j){
        int n=arr[i];
        arr[i]=arr[j];
        arr[j]=n;
    }
    public void print(){
        System.out.print("[");
        for (int i = 0; i <size ; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println("]");
    }
}
